package algorithm.sort;

import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2021/1/23 11:31
 * @Version 1.0
 */
public class MergeSort3 {
    public static void main(String[] args) {
        int[] arr = {3, 10, 22, 2, 1, 5, 9, 12, 1};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr){
        if(arr.length <= 1){
            return ;
        }

        for(int i = 1; i < arr.length; i *= 2){
            int pre = 0;
            while(pre < arr.length){
                //第一段的开始
                int m = pre;
                //第二段的开始
                int n = pre + i;
                merge(arr, m, n, i);

                //下一轮的开始
                pre = n + i;
            }
        }
    }

    public static void merge(int[] arr, int aStart, int bStart, int len){
        int[] temp = new int[2 * len];
        int i = aStart;
        int iEnd = Math.min(arr.length, aStart + len);
        int j = bStart;
        int jEnd = Math.min(arr.length, bStart + len);
        int cnt = 0;
        while(i < iEnd && j < jEnd){
            if(arr[i] <= arr[j]){
                temp[cnt++] = arr[i++];
            }
            else {
                temp[cnt++] = arr[j++];
            }
        }
        while(i < iEnd){
            temp[cnt++] = arr[i++];
        }
        while(j < jEnd){
            temp[cnt++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, aStart, cnt);
    }
}
